/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年12月28日
*   描    述：
*   
================================================================*/


#include <iostream>

using namespace std;

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if( !root )
            return;

        TreeLinkNode *cur = root;
        TreeLinkNode *next = NULL;
        TreeLinkNode *head = NULL;

        while( cur ){
            while( cur ){
                if( cur->left ){
                    if( !next ){
                        next = cur->left;
                    }
                    else{
                        head->next = cur->left;
                    }
                    
                    head = cur->left;
                }    

                if( cur->right ){
                    if( !next ){
                        next = cur->right;
                    }else{
                        head->next = cur->right;
                    }
                    
                    head = cur->right;
                }

                cur = cur->next;
            }
            
            cur = next;
            next = NULL;
        }


    }
};
